package com.dataStructure.并查集;

/**
 * 在Union的过程中，可能会出现树不平衡的情况，甚至退化成链表
 *
 * 有2种常见的优化方案
 *  1.基于size的优化：元素少的树 嫁接到 元素多的树
 *      基于size的优化，也可能会存在树不平衡的问题
 *  2.基于rank的优化：矮的树 嫁接到 高的树
 */

@SuppressWarnings("all")
public class 并查集_QuickUnion_Rank优化 extends 并查集_QuickUnion{

    private int[] ranks;

    public 并查集_QuickUnion_Rank优化(int capacity) {
        super(capacity);

        //初始化每棵树的高度
        ranks = new int[capacity];
        for (int i = 0; i < ranks.length; i++) {
            ranks[i] = 1;
        }
    }

    @Override
    public void union(int v1, int v2) {

        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;

        //比较两棵树的高度
        if (ranks[p1] < ranks[p2]){
            //如果p1的高度小于p2的高度，则将p1嫁接到p2上
            parents[p1] = p2;
        } else if (ranks[p1] > ranks[p2]) {
            //如果p1的高度大于p2的高度，则将p2嫁接到p1上
            parents[p2] = p1;
        }else {
            //如果两棵树的高度一样高，则随意嫁接即可，并将被嫁接的树高度加一
            parents[p1] = p2;
            ranks[p2] += 1;
        }
    }
}
